Міністерство освіти і науки України Національний університет “Львівська політехніка” Кафедра ЕОМ  КУРСОВА РОБОТА з дисципліни: «Паралельні та розподілені обчислення» на тему: «Паралельне виконання операцій множення матриць» Залікова книжка № 1009546 Львів 2014р. Завдання Розробити структуру та описати процедуру перемноження матриці А(розмірністю n1*n2) на матрицю В (розмірністю n2*n3) на заданій структурі. Для цієї структури визначити час виконання алгоритму, відсоток послідовної частини алгоритму та ефективність алгоритму для значень, що наведені в таблиці. Для визначення завдання були виконані такі дії: 1. Визначення розмірів матриць. Для цього потрібно було провести декодування літер, які задавались згідно номеру групи: n1=3П-"Х" , n2=2І-"O", n3=4Б-"H" – КІ-42 Згідно з таблицею декодування літер розмірностей: n1 = 240 n2 = 248 n3 = 67 А(240*248) В(248*67) С(240*67) 2. Структура задається виразом: 5b-12b-6b-11b-8b-1b-3b-13b – КІ-42 де «nb»- номер букви П.І.Б студента. Для того, щоб сформувати задану структуру, скористаємось таблицею 1.1., щоб отримати відповідні літери. Після цього розкодуємо їх задопомогою таблиці кодування букв. Таблиця 1.1. - Порядкові номери літер прізвища, імені та по-батькові 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  К У Х А Р Б О Г Д А Н І В А Н О В И Ч  6  7  1 3  5   4 2  8        Порядк літер прізвища, імені та по-батькові з таблиці 1.1.: РІБНГКХА Звідси формуємо таблицю декодування табл. 1.2, та матрицю зв’язків табл. 1.3. Таблиця 1.2.Таблиця декодування Р = 93 01011101  І = 223 11011111  Б = 35 00100011  Н = 134 10000110  Г = 74 01001010  К = 47 00101111  Х = 127 01111111  А = 27 00011010   Таблиця 1.3.Матриця зв’язків ms 1 2 3 4 5 6 7 8  1 0 1 0 1 1 1 0 1  2 1 0 0 1 1 1 1 1  3 0 0 0 0 0 0 1 1  4 1 0 0 0 0 1 1 0  5 0 1 0 0 0 0 1 0  6 0 0 1 0 1 0 1 1  7 0 1 1 1 1 1 0 1  8 0 0 0 1 1 0 1 0   3. Визначення типу пам’яті: Номер залікової книжки: 1009546 (25 mod 3) + 1 = 2 – завантаження через один процесор. Співвідношення часових параметрів: tU = 10tS  = 6tP =5tZ = 7tW Анотація В даній курсовій роботі завданням було розробка алгоритму паралельного множення двох матриць розмірами 240х248 і 248х67 на розподіленій комп’ютерній системі із восьми процесорів, при чому завантаження і вивантаження відбувалось через один із них. Такий алгоритм може бути ефективним в системах з обмеженим доступом до пам’яті. Для реалізації паралельного алгоритму множення матриць було використано інтерфейс передачі повідомлень (МРІ) між процесами, оскільки він має широкі можливості. Для програмної реалізації алгоритму було обрано мову С++, з використаннямMPI. Наведені граф-схеми виконання алгоритму, схеми планування обчислень і блок-схеми програми множення матриць пояснюють реалізацію даного алгоритму більш детально.  Зміст Вступ 6 1. Теоретичний розділ 7 1.1 Матричні обчислення 7 1.2 Інтерфейс передачі повідомлень 10 1.3 Сучасні методи та інструменти для паралельної обробки................11 1.3.1 Технологія NVIDIA® CUDA™..................................................12 2. Розробка граф-схеми виконання множення матриць 13 3. Розробка функціональної схеми 18 4. Розрахунковий розділ 23 4.1 Визначення розмірності підматриць 23 4.2 Розрахунок часу виконання послідовного алгоритму 24 4.3 Розрахунок часу виконання паралельного алгоритму 25 4.4 Порівняння ефективності 25 5.Розробка програми 26 5.1 Вибір середовища 26 5.2 Опис використаних функцій MPI 26 5.3 Розробка загальної блок-схеми програми 31 Висновки 32 Список використаної літератури 33 Додаток 39  Вступ Доволі значна частина математичних моделей, що розглядаються при вирішенні проблем, породжених промисловістю, наукою та технікою, зводяться до задач математичної фізики. В наші часи чи не єдиним способом їх розв’язання є чисельні методи та використання ЕОМ. Проте ...